package com.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
 * 如果可以，请返回 true；否则，返回 false。
 * <p>
 * 输入：nums = [1,2,3,3,4,4,5,6], k = 4 输出：true 解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。
 */
public class No1296 {
    public boolean isPossibleDivide(int[] nums, int k) {
        if (nums.length % k != 0) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Arrays.sort(nums);
        for (int num : nums) {
            if (!map.containsKey(num) || map.get(num) == 0) {
                continue;
            }
            for (int i = 0; i < k; i++) {
                int nexNum = num + i;
                if (!map.containsKey(nexNum) || map.get(nexNum) == 0) {
                    return false;
                }
                map.put(nexNum, map.get(nexNum) - 1);
            }
        }
        return true;
    }
}
